package 中等.贪心思想;

/**
 * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-swap/
 */
public class 最大交换_670 {

    public static void main(String[] args) {

        最大交换_670 service = new 最大交换_670();

        System.out.println(service.efficientMaximumSwap(2737));

    }

    /**
     * 贪心思想
     * 对于一个数字 num 2736 ，将它转成一个数组 nums[2,7,3,7]
     * 从左往右遍历 curIdx，如果在范围 [curIdx+1,end] 中存在某个索引
     * targetIdx 使得 nums[targetIdx] > nums[curIdx] ，
     * 1，如果存在多个满足条件，优先取最大值索引
     * 2，如果存在多个最大值，优先取索引最大的那一个
     *
     * @param num
     * @return
     */
    public int efficientMaximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char preVal = chars[i];
            // 找到 [i+1,end] 中大于 preVal 的最大索引，有相同值取索引较大的那个
            int idx = -1;
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[j] > preVal) {
                    if (idx == -1) {
                        idx = j;
                        continue;
                    }
                    if (chars[j] >= chars[idx]) {
                        idx = j;
                    }
                }
            }
            if (idx != -1) {
                replace(chars, i, idx);
                break;
            }
        }
        return Integer.valueOf(new String(chars));
    }

    /**
     * 得出所有交换后的数字可能性，取最大值
     *
     * @param num
     * @return
     */
    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int max = num;

        for (int i = 0; i < chars.length; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                replace(chars, i, j);

                max = Math.max(max, Integer.valueOf(new String(chars)));

                // 还原数字
                replace(chars, i, j);
            }
        }

        return max;
    }

    private void replace(char[] chars, int idx1, int idx2) {
        char val1 = chars[idx1];
        chars[idx1] = chars[idx2];
        chars[idx2] = val1;
    }

}
